package com.itzmn.datastructure.sort;

/**
 * @Author: 张梦楠
 * @Date: 2018/11/9 12:43
 * 简书：https://www.jianshu.com/u/d611be10d1a6
 * 码云：https://gitee.com/zhangqiye
 * @Description:  插入排序
 *
 * 思路：
 *  将前面的序列看做有序的，将后面的数据，向前插入有序序列中，后面插入前面，
 *  判断是否小于，前面的元素，就一直后移，
 */
public class InsertSort {


    public static void main(String[] args) {
        int[] ints = {5,2,4,6,3,7,1};
        long l = System.currentTimeMillis();
        new InsertSort().insertSort(ints,ints.length);
        System.out.println(System.currentTimeMillis()-l);
    }

    /**
     * 直接插入排序
     * @param arrs  数组
     * @param len  数组长度
     */
    public void insertSort(int arrs[],int len){

        for (int i=1;i<len;i++){
            //保存当前位置的数据
            int tem = arrs[i];

            int j=i-1;
            //如果后面一个数小于前面一个数，就交换位置
            while (j>=0 && arrs[j]>tem){
                arrs[j+1] = arrs[j];
                j--;
            }
            arrs[j+1]=tem;

            log(arrs);
        }
    }

    public void log(int arrs[]){

        for (int i=0;i<arrs.length;i++){
            System.out.print(arrs[i]+" ");
        }
        System.out.println();
    }



}
